"""
Problem 24: https://projecteuler.net/problem=24

A permutation is an ordered arrangement of objects. For example, 3124 is one
possible permutation of the digits 1, 2, 3 and 4. If all of the permutations
are listed numerically or alphabetically, we call it lexicographic order. The
lexicographic permutations of 0, 1 and 2 are:

    012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5,
6, 7, 8 and 9?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.8.3
@creat_time = 2022/5/9
'''

def solution(index: int = 1000000, num: int = 10) -> str :
    '''
    index <= num !    

    10! = 3628800

    1000000 = c10 * c10 + c9 * (9!) + c8 * (8!) + c7 * (7!) + ... + c1 * (1!)
        (1). c_i <= i, otherwise, increase c_(i+1)
        (2). c10 = 0 or (c10 = 1 , rest c_i = 0), 
             otherwise, surpass all the permutations
    
    e.g.
        consider some cases,
        (1). the first(index = 1) permutation: 0123456789
             c[10 ~ 1] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
        (2). the last(index = 10!) permutation: 9876543210
             c[10 ~ 1] = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        (3). the sixth(index = 6) permutation: 012345(6987)
             c[10 ~ 1] = [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
        (4). the 23th(index = 23) permutation: 012345(9867)
             c[10 ~ 1] = [0, 0, 0, 0, 0, 0, 0, 3, 2, 1]
        (5). index = 1000000
             c[10 ~ 1] = [0, 2, 6, 6, 2, 5, 1, 2, 2, 0]
             
             c9 = 2: 0*****(9!), 1*****(9!), 
                     now is 2*****
             c8 = 6: 20****(8!), 21****(8!), 23****(8!), 24****(8!), 
                     25****(8!), 26****(8!),
                     now is 27****  <= skip 22, not repeat
             c7 = 6: 260***(7!), 261***(7!), 263***(7!), 264***(7!), 
                     265***(7!), 267***(7!), 
                     now is 268***  <= skip 266, not repeat
            
             which shows:
             # nomal case: ci determine the digit(i+1), such as, 
             
                    d10, d9, d8, d7, d6, d5, d4, d3, d2, d1
                      \   \   \   \   \   \   \   \   \
                       c9, c8, c7, c6, c5, c4, c3, c2, c1
            
                   * d1 is certain if d10 ~ d2 are determined.
             
             # sepcial case: [..., k(i), 0, 0, ...] means 
               inverted order of [c_i-1, c_i-1, ...] and 
               map of (k(i), di) is difference, 
               see(3), at normal case , is 012345(7689)
    
    ...
    
    >>> print(solution(1))
    0123456789
    >>> print(solution(4, 3))
    120
    >>> print(solution(3628800))
    9876543210
    >>> print(solution(3628799))
    9876543201
    '''
    
    ############# compute bases = [9!,8!,...,1!]
    bases = []
    res = 1
    for i in range(1, num+1):
        res = i * res
        bases.append(res)
    bases.reverse()
    
    if index > bases[0]:
        raise ValueError('index > n!')
    elif index == bases[0]:
        return ''.join(list(map(str,range(num-1, -1, -1))))
    else:
        bases = bases[1:]  # remove bases[0] = 10!
        # print('bases = ',bases)
        # bases = [362880, 40320, 5040, 720, 120, 24, 6, 2, 1]
    
    
    ############# compute c[9 ~ 1] for num accroding bases above
    c = [0] * (num-1)
    i = 0
    while index != 0:
        c[i], index = divmod(index, bases[i])
        i += 1
    # print('c=',c)
    # c = [2, 6, 6, 2, 5, 1, 2, 2, 0]
        
    
    
    ############# map c[9 ~ 1] to digits
    
    res = []
    rest = list(range(num))
    
    # handle such as [..., k(i), 0, 0, ...]
    for i in range(num-2, -1, -1):
        if c[i]:
            k = i
            # print('k= ',k)
            break
    
    
    # nomal case
    for i in range(k):
        res.append(rest[c[i]])
        rest.remove(res[-1])
    
    # sepcial case as [..., k(i), 0, 0, ...]
    res.append(rest[c[k]-1])
    rest.remove(res[-1])
    rest.reverse()
    # print('rest',rest)
    res = res + rest
    
    return ''.join(list(map(str,res)))
        

    

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    
    print(solution())
    # 2783915460

    
    
    
    


    


